import java.util.concurrent.LinkedTransferQueue;

public class Sort6 {
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    //每一次划分的过程都在将元素放在最终的位置上
    private static void quick(int[] array,int start,int end) {
        //递归的退出条件
        if (start >= end) {
            return;
        }
        //按基准值对数组划分
        int pivot = partition(array,start,end);
        //递归分别排[left,pivot) 和(piovt,right]
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    //按基准值进行划分：主要就是这里的思想有不同
    //Hoare版
    private static int partition(int[] array,int left,int right) {
        //基准
        int tmp = array[left];
        //记录下left：为了最后将基准和left位置的元素交换
        int i = left;

        while (left < right) {
            //从右边开始向左找比基准tmp小的值
            //如果右边的所有值都比基准值大，right就会走到-1下标越界，所以要加上left<right
            while (left<right && array[right] >= tmp) {//要加等号？
                right--;
            }

            while (left<right && array[left] <= tmp) {
                left++;
            }
            //right下标找到的元素与left找到的下标进行交换
            swap(array,left,right);
        }
        //将基准值放到确定的位置上
        swap(array,left,i);
        //返回left和right相遇的位置
        return left;
    }
    //挖坑法
    private static int partition2(int[] array,int left,int right) {
        //挖坑，并把坑内元素记录下来
        int tmp = array[left];

        while (left < right) {

            while (left < right && array[right] >= tmp) {
                right--;
            }
            //优化：排除自己给自己赋值
            if (left==right) break;
            //右边找到小于基准的值，把它放在tmp对应的坑里
            array[left] = array[right];

            while (left < right && array[left] <= tmp) {
                left++;
            }
            if (left==right) break;
            //同理在左边找
            array[right] = array[left];
        }
        //补坑
        array[left] = tmp;
        return left;
    }
    //前后指针
    private static int partition3(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[prev++] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}
